# source: https://leetcode.cn/problems/count-number-of-texts/ 记忆化搜索 动态规划
from functools import cache


class Solution:
    def countTexts(self, pressedKeys: str) -> int:
        set1 = ['2', '3', '4', '5', '6', '8']
        i, j = 0, 0
        ans = 1
        @cache
        def dfs(value):
            if value == 0:
                return 1
            cnt = 0
            for v in [1, 2, 3]:
                if value - v >= 0:
                    cnt += dfs(value - v) 
            return cnt % (pow(10, 9)+7)

        @cache
        def dfs1(value):
            if value == 0:
                return 1
            cnt = 0
            for v in [1, 2, 3, 4]:
                if value - v >= 0:
                    cnt += dfs1(value - v)
            return cnt % (pow(10, 9)+7)

        while j < len(pressedKeys):
            while j < len(pressedKeys) and pressedKeys[j] == pressedKeys[i]:
                j += 1
            cnt = j - i
            ans *= (dfs(cnt) if pressedKeys[i] in set1 else dfs1(cnt))
            ans %= (pow(10, 9)+7)
            i = j
            j += 1
        return ans
# DP 爬楼梯
MOD = 1_000_000_007
f = [1, 1, 2, 4]
g = [1, 1, 2, 4]
for _ in range(10 ** 5 - 3):  # 预处理所有长度的结果
    f.append((f[-1] + f[-2] + f[-3]) % MOD)
    g.append((g[-1] + g[-2] + g[-3] + g[-4]) % MOD)

class Solution:
    def countTexts(self, pressedKeys: str) -> int:
        ans = 1
        for ch, s in groupby(pressedKeys):
            m = len(list(s))
            ans = ans * (g[m] if ch in "79" else f[m]) % MOD
        return ans
